495. Teemo Attacking

题目 495. Teemo Attacking

思路分析

用set计有多少个点 会tle

可以用区间合并

代码实现

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int time : timeSeries){
            map.put(time,map.getOrDefault(time,0)+1);
            for(int i=1;i<duration;i++){
                map.put(time+i,map.getOrDefault(time+i,0)+1);
            }
        }
        return map.size();
    }
}

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        HashSet<Integer> set = new HashSet<>();
        
        for (int time : timeSeries) {
            for (int i = 0; i < duration; i++) {
                set.add(time + i); 
            }
        }
        
        return set.size();
    }
}

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) return 0;

        int totalTime = 0;
        
        int start = timeSeries[0];
        int end = timeSeries[0] + duration;

        for (int i = 1; i < timeSeries.length; i++) {
            int newStart = timeSeries[i];
            int newEnd = timeSeries[i] + duration;

            if (newStart < end) {
                end = newEnd; 
            } else {
                totalTime += (end - start);
                start = newStart;
                end = newEnd;
            }
        }
        
        totalTime += (end - start);

        return totalTime;
    }
}

同类题型

视频讲解